package 二叉树相关问题.层次遍历;

import java.util.LinkedList;
import java.util.Queue;

public class 奇偶数 {

    public boolean isEvenOddTree(TreeNode root) {
        if(root == null) return true;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        int pre=root.val;
        boolean oddFlag=true, firstFlag=true;
        while(!queue.isEmpty()){
            for(int i=queue.size();i>0;i--){
                TreeNode node=queue.poll();
                if((oddFlag && node.val%2 == 0)||(!oddFlag && node.val%2 == 1)){//偶数层不能为偶数，奇数层不能为奇数
                    return false;
                }
                if(firstFlag){//每层首个节点不用比较大小
                    firstFlag=false;
                }else{//保证偶数层严格递增，奇数层严格递减
                    if((oddFlag && node.val <= pre)||(!oddFlag && node.val >= pre)){
                        return false;
                    }
                }
                pre=node.val;
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            firstFlag=true;
            oddFlag=!oddFlag;
        }
        return true;
    }
}
